1. 题目
题目链接:P2014「[CTSC1997]选课」 。
题目描述
在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有 N N N 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程 a a a 是课程 b b b 的先修课即只有学完了课程 a a a ,才能学习课程 b b b )。一个学生要从这些课程里选择 M M M 门课程学习,问他能获得的最大学分是多少?
输入格式
第一行有两个整数 N N N ,M M M 用空格隔开。(1 ≤ N ≤ 300 1 \leq N \leq 300 1 ≤ N ≤ 300 ,1 ≤ M ≤ 300 1 \leq M \leq 300 1 ≤ M ≤ 300 )
接下来的 N N N 行,第 I + 1 I+1 I + 1 行包含两个整数 k i k_i k i 和 s i s_i s i ,k i k_i k i 表示第 I I I 门课的直接先修课,s i s_i s i 表示第 I I I 门课的学分。若 k i = 0 k_i=0 k i = 0 表示没有直接先修课(1 ≤ k i ≤ N 1 \leq {k_i} \leq N 1 ≤ k i ≤ N ,1 ≤ s i ≤ 20 1 \leq {s_i} \leq 20 1 ≤ s i ≤ 20 )。
输出格式
只有一行,选 M M M 门课程的最大得分。
输入输出样例
输入 #1
1 2 3 4 5 6 7 8 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2
输出 #1
2. 题解
分析
树上 dp + 背包问题的结合,即树上背包。有题意可知,最终这些课程构成一个森林,我们不妨将 0 0 0 号结点看作所有树的根,其学分为 0 0 0 ,则我们将森林转为一棵树来处理:
f [ i ] [ j ] = max 1 ≤ k ≤ j − 1 { f [ i ] [ j ] , f [ i ] [ j − k ] + f [ v ] [ k ] } f[i][j] = \max_{1 \leq k \leq j-1}\{f[i][j], f[i][j-k]+f[v][k]\}
f [ i ] [ j ] = 1 ≤ k ≤ j − 1 max { f [ i ] [ j ] , f [ i ] [ j − k ] + f [ v ] [ k ]}
即对于当前结点 i i i 有 j j j 的容量、分 k k k 的容量给 v v v 子树得到的最大学分。
注意
首先,对于每个孩子 v v v 而言,j j j 应当从最大递减逆序枚举,因为需要保证 f [ i ] [ j − k ] f[i][j-k] f [ i ] [ j − k ] 的最优解不是来源于 v v v 子树(因为 f [ v ] [ k ] f[v][k] f [ v ] [ k ] 已经是来源于 v v v 子树的)。
其次,遍历每个孩子 v l v_l v l 时 j j j 的范围时不一样的。因为对于已经遍历过的子树而言,我们需要考虑其也有可能对最优解产生贡献,因此需要将 j j j 的范围扩大到包括所有已遍历的子树大小(但不能超过 m + 1 m+1 m + 1 )。设 r e s res res 为已经遍历的子树的大小之和,则 j j j 的范围为
j ∈ [ 1 , m i n ( r e s , m + 1 ) ] j \in [1,min(res,m+1)]
j ∈ [ 1 , min ( res , m + 1 )]
最后,需要计算结点 i i i 所有可能容量的最优解,然后向上更新父结点。以此类推。
求解过程可以采用自顶向下的方法,即利用树的递归性质,采用 DFS 遍历整棵树,每次遍历完子树后再更新当前结点;也可以采用自底向上的方法,首先构建一个队列,将孩子数为 0 0 0 的结点加入队列中。然后从队列中取出结点开始更新,每次更新完都将父结点的孩子树减 1 1 1 ,然后将孩子树为 0 0 0 的父结点加入队列中(本质是一个拓扑序列,将父子结点的边看作是孩子到父亲的有向边)。
代码
DFS 计算子树最优解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <bits/stdc++.h> #define ll int #define MAXN 305 using namespace std;ll cnt; ll head[MAXN]; struct edge { ll to; ll next; }e[MAXN]; void init () { cnt = 0 ; memset (head, -1 , sizeof (head)); } void addEdge (ll u, ll v) { e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++; } ll k[MAXN]; ll s[MAXN]; ll dp[MAXN][MAXN]; ll dfs (ll u, ll m) { ll res = 1 ; dp[u][1 ] = s[u]; for (ll i = head[u]; i != -1 ; i = e[i].next) { ll curres = dfs (e[i].to, m-1 ); for (ll j = min (res, m); j; --j) { for (ll ii = 1 ; ii <= curres && j+ii <= m; ++ii) { dp[u][j+ii] = max (dp[u][j+ii], dp[u][j] + dp[e[i].to][ii]); } } res += curres; } return res; } int main () { ll n, m; init (); scanf ("%d%d" , &n, &m); for (ll i = 1 ; i <= n; ++i) { ll ki, si; scanf ("%d%d" , &ki, &si); k[i] = ki; s[i] = si; addEdge (ki, i); } dfs (0 , m+1 ); printf ("%d\n" , dp[0 ][m+1 ]); return 0 ; }
拓扑排序计算子树最优解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include <bits/stdc++.h> #define ll int #define MAXN 305 using namespace std;ll cnt; ll head[MAXN]; struct edge { ll to; ll next; }e[MAXN]; void init () { cnt = 0 ; memset (head, -1 , sizeof (head)); } void addEdge (ll u, ll v) { e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++; } ll k[MAXN]; ll s[MAXN]; ll in[MAXN]; ll sz[MAXN]; ll dp[MAXN][MAXN]; void answer (ll n, ll m) { queue <ll> q; for (int i = 0 ; i <= n; ++i) { if (!in[i]) { dp[i][1 ] = s[i]; sz[i] = 1 ; --in[k[i]]; ++sz[k[i]]; if (!in[k[i]]) { ++sz[k[i]]; q.push (k[i]); } } } while (q.size ()) { ll p = q.front (); q.pop (); ll res = 1 ; dp[p][1 ] = s[p]; for (ll i = head[p]; i != -1 ; i = e[i].next) { ll u = e[i].to; for (ll j = min (res, m+1 ); j; --j) { for (ll d = 1 ; d <= sz[u] && d+j <= m+1 ; ++d) { dp[p][d+j] = max (dp[p][d+j], dp[p][j]+dp[u][d]); } } res += sz[u]; } --in[k[p]]; sz[k[p]] += sz[p]; if (!in[k[p]]) { ++sz[k[p]]; q.push (k[p]); } } } int main () { ll n, m; init (); scanf ("%d%d" , &n, &m); for (ll i = 1 ; i <= n; ++i) { ll ki, si; scanf ("%d%d" , &ki, &si); k[i] = ki; s[i] = si; ++in[ki]; addEdge (ki, i); } answer (n, m); printf ("%d\n" , dp[0 ][m+1 ]); return 0 ; }